1. Field of the Invention
The present invention relates generally to an adder for adding a plurality of bits. More specifically, the invention relates to an adder for adding partial products at the same place in multiplication.
2. Description of the Related Art
Conventionally, an array type parallel multiplication system is used when a n-bit multiplicand X (=Xnxe2x88x9212nxe2x88x921+ . . . +X12+X0) and a n-bit multiplier Y (=Ynxe2x88x9212nxe2x88x921+ . . . +Y12+Y0) are multiplied together. In this array type parallel multiplication system, n2 AND gates are used to multiply each of bit values Xi(i=0, . . . , nxe2x88x921) of the multiplicand X by each of bit values Yj(j=0, . . . , nxe2x88x921) of the multiplier Y to derive partial products Pij(=Xixc2x7Yj), which are added in each place. For the addition of the partal products, arrayed full adders are used, and carry signals over the partial products are ripple carry connections.
Thus, in the array type multiplication system, the arrayed full adders are used for adding the partial products, and the carry signals over the partial products are the ripple carry connections. Therefore, it is not possible to add its own place unless a carry signal is received from a full adder of a lower place by 1. This is much problem to accelerate operation.
It is therefore an object of the present invention to eliminate the aforementioned problems and to provide an adder capable of adding a plurality of bits at high speed.
In order to accomplish the aforementioned and other objects, according to one aspect of the present invention, an adder comprises: comparing means for comparing values of n input signals, each of which comprises 1-bit data, with first to n-th predetermined values which are different from each other; a non-volatile memory having first to n+1-th word lines, m (2mxe2x89xa7n+1) bit lines which are provided so as to intersect the word lines, and memory cells, each of which is provided at an intersection of each of the word lines and each of the bit lines and each of which has stored 1-bit data; and selecting means for selecting one of the n+1 word lines on the basis of n comparison results of the comparing means to activate the selected word line.
The non-volatile memory may store predetermined data in each of the memory cells connected to the i-th (i=1, . . . , n+1) word line, and output m-bit data indicative of a binary number corresponding to ixe2x88x921 via the first to m-th bit lines when the i-th word line is selected.
The i-th (i=1, . . . , n) predetermined value may be greater than ixe2x88x921 and less than i, and the comparing means has first to n-th comparators, the i-th (i=1, . . . , n) comparator determining whether the number of input signals having a truth value of 1 out of the n input signals exceeds the first predetermined value, and outputting a i-th comparison result indicative signal, and the selecting means selecting one of the word lines on the basis of the first to n-th comparison result indicative signals.
The selecting means may have a first inverting gate for inverting the first comparison result indicative signal to output an inverted signal to the first word line, and a second inverting gate for inverting the inverted signal of the n-th comparison result indicative signal to output an inverted signal to the n+1-th word line, and the i-th (i=1, . . . , nxe2x88x921) NOR gate may carry out a NOR operation on the basis of the inverted signal of the i-th comparison result indicative signal and the i+1-th comparison result indicative signal to output an operation result to the i+1-th word line.
The i-th (i=1, . . . , n) comparator may comprise: first and second transistors of a first conductive type, each of the first and second transistors having a source, to which a first power supply voltage is applied; a third transistor of a second conductive type which is different from the first conductive type, the third transistor having a drain connected to a drain of the first transistor, and a gate connected to a gate of the first transistor and a drain of the second transistor; a fourth transistor of the second conductive type, the fourth transistor having a drain connected to the drain of the second transistor, and a gate connected to a gate of the second transistor and the drain of the first transistor; a fifth transistor of the second conductive type, the fifth transistor having a source connected to a second power supply voltage which is different from the first power supply voltage, and a gate for receiving an enable signal from the outside; a first transistor group including i transistors of the second conductive type, which are connected in parallel between a source of the third transistor and a drain of the fifth transistor, each of the i transistors having a gate, to which the first power supply voltage is applied; and a second transistor group including n transistors of the second conductive type, which are connected in parallel between a source of the fourth transistor and the drain of the fifth transistor, and wherein a j-th (j=1, . . . , n) input signal out of the n input signals is applied to a gate of a j-th transistor of the second transistor group, each of the n transistors of the second transistor group having the same current driving ability, one of the i transistors of the first transistor group having a current driving ability which is less than that of each of the n transistors of the second transistor group if i=1, each of transistors other than the one of the i transistors of the first transistor group having a current driving ability which is equal to that of each of the n transistors of the second transistor group and which is greater than that of the one of the i transistors of the first transistor group if ixe2x89xa01, and the i-th comparison result indicative signal being outputted from the drain of the first transistor, and an inverted signal of the i-th comparison result indicative signal being outputted from the drain of the second transistor.
According to another aspect of the present invention, a multiplier includes at least one adder comprising: comparing means for comparing values of n input signals, each of which comprises 1-bit data, with first to n-th predetermined values which are different from each other; a non-volatile memory having first to n+1-th word lines, m (2mxe2x89xa7n+1) bit lines which are provided so as to intersect the word lines, and memory cells, each of which is provided at an intersection of each of the word lines and each of the bit lines and each of which has stored 1-bit data; and selecting means for selecting one of the n+1 word lines on the basis of n comparison results of the comparing means to activate the selected word line, and the adder is used for adding partial products at the same place.